package com.leetcodehot.problems;

public class problems1901 {
    /**
     * 一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。
     * <p>
     * 给你一个 从 0 开始编号 的 m x n 矩阵 mat ，其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置 [i,j] 。
     * <p>
     * 你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。
     * <p>
     * 要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法
     */

    /**
     * 最核心的点在于 如何去进行二分思路。本题第一步是暴力的话 从小走到大，逐个判断。
     * 压缩出来就是某行最大值，看成是必经之路。根据上下之一的位置来判断最终峰顶应该在上面还是下面。
     */
    public int[] findPeakGrid(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int left = -1;
        int right = m - 1;
        while (left + 1 < right) {
            int i = left + (right - left) / 2;
            int j = indexOfMax(mat[i]);
            if (mat[i][j] > mat[i + 1][j]) {
                right = i;
            } else {
                left = i;
            }
        }
        return new int[]{right, indexOfMax(mat[right])};
    }

    private int indexOfMax(int[] a) {
        int idx = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > a[idx]) {
                idx = i;
            }
        }
        return idx;
    }
}
